package com.xiaoyu.binaryTree;


/**
 * @program: DS_and_A
 * @description:
 * 给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
 *
 * 本题中，一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。
 *
 * @author: YuWenYi
 * @create: 2021-05-18 10:31
 **/
public class SortedLinkedArrayToBST_109 {
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) return null;
        ListNode fast = head;
        ListNode slow = head;
        ListNode preSlow = null;  //记录slow的前一个结点
        //获取中间结点
  /*      while (fast.next!=null){
            fast = fast.next;
            if (fast.next!=null){
                fast = fast.next;
            }
            preSlow = slow;
            slow = slow.next;
        }*/
        while (fast!=null && fast.next!=null){
            preSlow = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        TreeNode root = new TreeNode(slow.val);  //以中间结点为根结点,开始创建AVL
        if (preSlow!=null){
            preSlow.next = null;   //将链表分为两段
            root.left = sortedListToBST(head);  //递归构建左子树
        }
        root.right = sortedListToBST(slow.next); //递归构建右子树
        return root;
    }


    public static void main(String[] args) {
        SortedLinkedArrayToBST_109 sa = new SortedLinkedArrayToBST_109();
        ListNode l1 = new ListNode(1,new ListNode(2,new ListNode(3,new ListNode(4))));

        TreeNode node = sa.sortedListToBST(l1);
        System.out.println(Inorder_94.inorderTraversal(node));
    }
}

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val,ListNode next) { this.val = val; this.next = next; }

    public boolean hasNext(){
        return next != null;
    }
}